%0 Conference Proceedings
%4 sid.inpe.br/banon/2005/07.10.17.42
%2 sid.inpe.br/banon/2005/07.10.17.42.13
%@doi 10.1109/SIBGRAPI.2005.5
%T A linear algorithm for exact pattern matching in planar subdivisions
%D 2005
%A Andrade Neto, Pedro Ribeiro de,
%A Guedes, André Luiz Pires,
%@affiliation Federal University of Paraná
%E Rodrigues, Maria Andréia Formico,
%E Frery, Alejandro César,
%B Brazilian Symposium on Computer Graphics and Image Processing, 18 (SIBGRAPI)
%C Natal, RN, Brazil
%8 9-12 Oct. 2005
%I IEEE Computer Society
%J Los Alamitos
%S Proceedings
%K sub-isomorphism, planar subdivisions.
%X Graph sub-isomorphism is a very common approach to solving pattern search problems, but this is a NP-complete problem. This way, it is necessary to invest in research of approximate solutions, or in special cases of the problem. Planar subdivisions can be considered as a special case of graphs, because, in addition to nodes and edges, there is a more rigid topology in relation to the order of the edges, arising to the concept of face. This work presents a linear algorithm for pattern search in planar subdivisions. The presented algorithm is based on a hybrid approach between the dual and the region adjacency graph (RAG) to represent the patterns, saving any additional storage cost. Thus, the patterns are looked over the search subdivision, using a region growing algorithm.
%@language en
%3 andradep_matchsubdivisions.pdf